package problems;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import lib.Fraction;


public class Euler033 extends AbstractEuler {

	@Override
	public Number calculate() {
		Set<Fraction> hadIt = new HashSet<Fraction>();
		List<Fraction> answers = new ArrayList<Fraction>();
		
		for (long numerator = 1; numerator < 100; numerator++) {
			next_denominator:
			for (long denominator = 1; denominator < 100; denominator++) {
				if (numerator >= denominator) continue; //only < 1
				Fraction base = new Fraction(numerator, denominator);
				if (hadIt.contains(base)) continue;
				hadIt.add(base);
				List<Fraction> waysOfWriting = new ArrayList<Fraction>();
				waysOfWriting.add(base);
				for (int i = 2; i * denominator <= 100; i++) {
					Fraction multiple = new Fraction(numerator * i, denominator * i);
					waysOfWriting.add(multiple);
				}
				if (waysOfWriting.size() <= 1) continue;

				//start at the back of the list and search for (wx/yz -> w/z)
				for (int i = waysOfWriting.size() - 1; i >= 0; i--) {
					Fraction biggest = waysOfWriting.get(i);
					if (biggest.getNumerator().longValue() < 10) {
						//System.out.println("found nothing for " + base + " before numerator became less than two digits");
						continue next_denominator;
					}
					if (biggest.getNumerator().longValue() % 10 != biggest.getDenominator().longValue() / 10) continue;
					Fraction simplified = new Fraction(biggest.getNumerator().longValue() / 10, biggest.getDenominator().longValue() % 10);
					if (simplified.equals(biggest)) {
						//System.out.println(base + " has " + biggest + " == " + simplified);
						answers.add(biggest);
						continue;
					}
				}
				//System.out.println(base + " has nothing");
			}
		}
		
		assertEquals("wrong amount of answers found;", 4, answers.size());
		
		Fraction answer = new Fraction(1, 1);
		
		for (Fraction f : answers) {
			answer = answer.times(f).normalized();
		}
		
		return answer.getDenominator().longValue();
	}

	@Override
	protected Number getCorrectAnswer() {
		return 100L;
	}

}
